package com.lwl.Algorithmic_data_structure.动态规划;

import org.junit.Test;

/**
 * 给一个数组，求把数组分为最接近的两部分，返回较小部分的和
 * 两部分 元素数量 要求最接近 ； 那么就要分奇偶了
 */
public class 平分数组2 {
    @Test
    public void test(){
        System.out.println(SplitSumClosed(new int[]{15 ,34 ,49 ,19 }));
    }
    public static int SplitSumClosed(int[] arr){
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return processDP(arr,sum/2);
//        if (arr.length % 2 == 0){
//            return process(arr, 0, sum / 2,arr.length / 2);
//        }else{
//            return Math.max(process(arr, 0, sum / 2,arr.length / 2),
//                    process(arr, 0, sum / 2,arr.length / 2 + 1));
//        }

    }

    private static int processDP(int[] arr,int target) {
        int N = arr.length;
        int M = (N + 1) / 2;
        int[][][] dp = new int[N+1][M+1][target + 1];
//        dp[arr.length][1...N][...] = -1
        for (int index = 0; index <= N; index++) {
            for (int picks = 0; picks <= M; picks++) {
                for (int rest = 0; rest <= target; rest++) {
                    dp[index][picks][rest] = -1;
                }
            }
        }
        for (int rest = 0; rest <= target; rest++) {
            dp[N][0][rest] = 0;
        }
        for (int index = N-1; index >= 0; index--) {
            for (int picks = 0; picks <= M; picks++) {
                for (int rest = 0; rest <= target; rest++) {
                    int p1 = dp[index+1][picks][rest];
                    int next = -1;
                    if (picks > 0 && rest >= arr[index]){
                        next = dp[index+1][picks-1][rest-arr[index]];
                    }
                    int p2 = next == -1 ? next : next + arr[index];
                    dp[index][picks][rest] = Math.max(p1,p2);
//                    int p1 = process(arr,index+1,rest,picks);
//                    int next = -1;
//                    if (rest >= arr[index]){
//                        next = process(arr,index+1,rest-arr[index],picks-1);
//                    }
//                    int p2 = next == -1 ? next : next + arr[index];
//                    return Math.max(p1,p2);
                }
            }
        }
//        PrintUtil.printArray(dp[0]);
        if (arr.length % 2 == 0){
            return dp[0][arr.length/2][target];
        }else{
            return Math.max(dp[0][(arr.length)/2 + 1][target],dp[0][(arr.length)/2][target]);
//            return Math.max(process(arr, 0, sum / 2,arr.length / 2),
//                    process(arr, 0, sum / 2,arr.length / 2 + 1));
        }
    }
    private static int process(int[] arr, int index, int rest, int picks) {
        if (index == arr.length){
            return picks == 0 ? 0 : -1;
//            return 0;
        }
        int p1 = process(arr,index+1,rest,picks);
        int next = -1;
        if (rest >= arr[index]){
            next = process(arr,index+1,rest-arr[index],picks-1);
        }
        int p2 = next == -1 ? next : next + arr[index];
        return Math.max(p1,p2);
    }
}
